package com.example.Arithmetic.Lettcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 日期：2023/12/28
 * 时间：21:12
 * 描述：第二种解法，控制桶的数量
 * (max-min)/range=数组长度  得
 * (max-min)/数组长度=range
 */
public class E01Lettcode164_2 {
    public int maximumGap(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        // 2. 桶排序
        int max = nums[0];
        int min = nums[0];
//        寻找最大值和最小值
        for (int i1 = 1; i1 < nums.length; i1++) {
            if (nums[i1] > max) {
                max = nums[i1];
            }
            if (nums[i1] < min) {
                min = nums[i1];
            }
        }
        int range = Math.max(1, (max - min) / (nums.length - 1));

        List<Integer>[] list = new ArrayList[(max - min) / range + 1];
//        初始化对象
        for (int i = 0; i < list.length; i++) {
            list[i] = new ArrayList();
        }
        for (int i : nums) {
            list[(i - min) / range].add(i);
        }
        int k = 0;
        for (List<Integer> l1 : list) {
            Collections.sort(l1);
            for (Integer ii : l1) {
                nums[k++] = ii;
            }
        }
        max = 0;
        for (int i = 1; i < nums.length; i++) {
            max = Math.max(max, nums[i] - nums[i - 1]);
        }
        return max;
    }

    public static void main(String[] args) {
        int[] arr1 = new int[]{10000000, 1};
        E01Lettcode164_1 e01Lettcode164 = new E01Lettcode164_1();
        int i = e01Lettcode164.maximumGap(arr1);
        System.out.println(i);
    }
}

